
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int MAXN = 80 + 5;
const int MAXK = 8;

int n, k, q;
int c[MAXN][MAXN];
LL f[MAXN][1 << MAXK];  // f[i][S]: 以i为根，联通S内所有点的最小代价
LL g[MAXN][1 << MAXK];  // g[i][S}: 枚举s之后，以i为根，联通S+{s}所有点的最小代价
bool used[MAXN];
LL ans[MAXN][MAXN];

int main() {
    scanf("%d%d", &n, &k);
    for (int i = 0; i <= n - 1; ++i) {
        for (int j = 0; j <= n - 1; ++j) {
            scanf("%d", &c[i][j]);
        }
    }
    
    // Step1. 求 f
    for (int i = 0; i <= n - 1; ++i) {
        for (int S = 0; S < (1 << k); ++S) {
            f[i][S] = 1e18;
        }
    }
    
    for (int i = 0; i <= k - 1; ++i) 
        f[i][1 << i] = 0;
        
    for (int S = 1; S < (1 << k); ++S) {
        for (int i = 0; i <= n - 1; ++i) {
            for (int T = (S - 1) & S; T; T = (T - 1) & S) {
                f[i][S] = min(f[i][S], f[i][T] + f[i][S ^ T]);
            }
        }

        for (int i = 0; i < n; ++i)
            used[i] = 0;
        for (int i = 1; i <= n - 1; ++i) {
            int v = -1;
            for (int j = 0; j < n; ++j) {
                if (!used[j] && (v == -1 || f[j][S] < f[v][S]))
                    v = j;
            }
            used[v] = 1;
            for (int j = 0; j < n; ++j) {
                f[j][S] = min(f[j][S], f[v][S] + c[v][j]);
            }
        }
    }

    // Step2. 对所有 (s,t) 处理
    for (int s = k; s <= n - 1; ++s) {
        // 我们现在的 g[i][S]: 的意思是包含 {S, s} 这些点
        for (int i = 0; i <= n - 1; ++i) {
            for (int S = 0; S < (1 << k); ++S) {
                g[i][S] = 1e18;
            }
        }
        g[s][0] = 0;
        
        for (int S = 0; S < (1 << k); ++S) {
            for (int i = 0; i <= n - 1; ++i) {
                for (int T = S; T; T = (T - 1) & S) {
                    // {S,s} = {S-T,s} + {T}
                    g[i][S] = min(g[i][S], g[i][S ^ T] + f[i][T]);
                }
            }

            for (int i = 0; i < n; ++i)
                used[i] = 0;
            for (int i = 1; i <= n - 1; ++i) {
                int v = -1;
                for (int j = 0; j < n; ++j) {
                    if (!used[j] && (v == -1 || g[j][S] < g[v][S]))
                        v = j;
                }
                used[v] = 1;
                for (int j = 0; j < n; ++j) {
                    g[j][S] = min(g[j][S], g[v][S] + c[v][j]);
                }
            }
        }
        
        for (int t = k; t <= n - 1; ++t) {
            ans[s][t] = g[t][(1 << k) - 1];
        }
    }

    int q;
    scanf("%d", &q);
    while (q--) {
        int s, t;
        scanf("%d%d", &s, &t);
        printf("%lld\n", ans[s - 1][t - 1]);
    }
    return 0;
}